// bfs 解决最短路问题
// 经典问题 - 边权为 1 的最短路问题，bfs 搜索目标坐标，返回搜索的步数
// 经典问题 - 基因序列变化，字符串每次改变一个字符，变化成最终的基因的最少次数。
// bfs 搜索所有可能变化情况，搜到有效变化，有效次数 + 1
// 经典问题 - 高尔夫球场砍树，需要将要砍的树按顺序排好，然后每两棵树之间进行一次 bfs

// 例题 4：
// 你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
//
//        0 表示障碍，无法触碰
//        1 表示地面，可以行走
//        比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
//        每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
//
//        你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
//
//        你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
//
//        可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
//
//        示例 1：
//
//
//        输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
//        输出：6
//        解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
//        示例 2：
//
//
//        输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
//        输出：-1
//        解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。
//        示例 3：
//
//        输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
//        输出：6
//        解释：可以按与示例 1 相同的路径来砍掉所有的树。
//        (0,0) 位置的树，可以直接砍去，不用算步数。
//
//
//        提示：
//
//        m == forest.length
//        n == forest[i].length
//        1 <= m, n <= 50
//        0 <= forest[i][j] <= 109

// 解题思路：
// 先将要砍的树的坐标进行排序，可以选择使用数组，也可以使用堆
// 从前往后遍历数组或者堆，每两棵高度相邻的树进行一次 bfs

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class CutOffTree {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m = 0;
    int n = 0;
    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->{
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int num = forest.get(i).get(j);
                if(num > 1) heap.offer(new int[]{i, j});
            }
        }
        int ret = 0;
        int x1 = 0; int y1 = 0;
        while(!heap.isEmpty()){
            int[] point = heap.poll();
            int x2 = point[0]; int y2 = point[1];
            int step = bfs(forest, x1, y1, x2, y2);
            if(step == -1) return -1;
            ret += step;
            x1 = x2; y1 = y2;
        }
        return ret;
    }
    public int bfs(List<List<Integer>> forest, int x1, int y1, int x2, int y2){
        if(x1 == x2 && y1 == y2) return 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] check = new boolean[m][n];
        queue.offer(new int[] {x1, y1});
        check[x1][y1] = true;
        int ret = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            ret++;
            for(int i = 0; i < size; i++){
                int[] point = queue.poll();
                int a = point[0];
                int b = point[1];
                for(int j = 0; j < 4; j++){
                    int x = a + dx[j];
                    int y = b + dy[j];
                    if(x >= 0 && x < m && y >= 0 && y < n){
                        int height = forest.get(x).get(y);
                        if(height != 0 && check[x][y] == false){
                            if(x == x2 && y == y2) return ret;
                            queue.offer(new int[] {x, y});
                            check[x][y] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
}
